package lc;
import java.util.*;
import org.junit.*;
public class Ex316 {
    /* 
    输入：s = "bcabc"
    输出："abc"
    示例 2：

    输入：s = "cbacdcbc"
    输出："acdb"
    */
    class Solution {
        public String removeDuplicateLetters1(String s) {
            Map<Character, Integer> map = new HashMap<>();
            char[] cs = s.toCharArray();
            int len = cs.length;
            for (int i = 0; i < cs.length; i++) {
                map.put(cs[i], map.getOrDefault(cs[i], 0) + 1);
            }
            StringBuilder sb = new StringBuilder();
            int l;
            char c;
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < len; i++) {
                if (!set.contains(cs[i])) {
                    while ((l = sb.length()) > 0 && (c = sb.charAt(l - 1)) > cs[i]
                     && map.get(c) > 0) { //map.get(c) > 0, 说明后面还有他，可以丢弃 
                        set.remove(c);
                        sb.setLength(l - 1);
                    }
                    sb.append(cs[i]);//无论如何，只要没有就添加
                    set.add(cs[i]);
                }
                map.put(cs[i], map.get(cs[i]) - 1);
            }
            return sb.toString();
        }

        public String removeDuplicateLetters(String s) {
            Map<Character, Integer> map = new HashMap<>();
            char[] cs = s.toCharArray();
            for (int i = 0; i < cs.length; i++) {
                map.put(cs[i], map.getOrDefault(cs[i], 0) + 1);
            }

            Stack<Character> stack = new Stack<>();
            Set<Character> set = new HashSet<>();
            char ch;
            //set中最多只存一个元素，且有被pop()时候，此时set不再含有，可以继续进栈
            for (char c: cs) {
                if (!set.contains(c)) {
                    while (!stack.isEmpty() && c < (ch = stack.peek()) && map.get(ch) > 0) {
                        set.remove(stack.pop());
                    }
                    set.add(c);
                    stack.push(c);
                }
                map.put(c, map.get(c) - 1);
            }
            // String.join("", stack);
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.insert(0, stack.pop());
            }
            //abacb  ab
            return sb.toString();
        }
    }
    
    @Test
    public void test() {
        Solution s = new Solution();
        // System.out.println(s.removeDuplicateLetters("cdadabcc"));   
        System.out.println(s.removeDuplicateLetters1("bcabc"));        
        System.out.println(s.removeDuplicateLetters1("abacb"));
    }
}
